<?php 
/** 
 * 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）


思路：使用一个辅助栈
      依次将压入序列，压入辅助栈
      在压入的过程中，如果当前压入后栈顶的值等于弹出序列的第一个值，例如（压入到4时，4等于弹出序列的第一个值）
      此时，弹出栈顶元素4，弹出序列的首位索引值更新为5
      此时弹出序列首位值5 != 栈顶元素3 所以压入5
      5 （栈顶）= 5 （弹出首位）
      弹出栈顶5 
      3 （栈顶）= 3 （弹出首位）
      弹出栈顶3
      2 （栈顶）= 2 （弹出首位）
      弹出栈顶2
      1 （栈顶）= 1 （弹出首位）
      弹出栈顶1
      左后辅助栈为空则证明弹出序列是压入序列的某一个弹出序列

      步数          辅助栈stack          压入        弹出           弹出栈首位
 *     1				1                 1          null           (4),5,3,2,1
 *     2               1,2                2          null           (4),5,3,2,1
 *     3              1,2,3               3          null           (4),5,3,2,1
 *     4             1,2,3,4              4          null           (4),5,3,2,1
 *     5              1,2,3              null         4             4,(5),3,2,1
 *     6             1,2,3,5              5          null           4,(5),3,2,1
 *     7              1,2,3              null         5             4,5,(3),2,1
 *     8               1,2               null         3             4,5,3,(2),1
 *     8                1                null         2             4,5,3,2,(1)
 *     9              empty              null         1             4,5,3,2,1,()
 *
 * 最后stack
  */



function IsPopOrder($pushV, $popV)
{
	if (!is_array($pushV) || !is_array($popV)) {
		exit('参数错误');
	}

    $pushCount = count($pushV);
    $popCount = count($popV);

    if ($pushCount == 0) {
    	exit('push 数组不能为空');
    }
    if ($popCount == 0) {
    	return false;
    }

    $stack = [];

    for ($i = 0,$j = 0;$i < $pushCount;$i++) {
    	array_push($stack, $pushV[$i]);
    	while ($j < $popCount && (count($stack) > 0) &&( $stack[count($stack) - 1] == $popV[$j])) {
    		array_pop($stack);
    		$j++;
    	}
    }

    return empty($stack);
}

$pushV = [1,2,3,4,5];
$popV = [4,5,3,2,1];
$popV = [3,2,1,4,5];

var_dump(IsPopOrder($pushV, $popV));


